1. Field of the Invention
The invention relates to curve tracing systems, and in particular to methods of extracting a smooth curve from noisy curve data.
2. Background Information
Noisy curves can be visually well defined but mathematically difficult to describe. Take FIG. 1 for example, the average person would not have any problem perceiving that it shows a curve that contains a peak and a valley. If a person were to trace the curve using a pen, they might typically use the following steps:                1. decide the general shape of the curve,        2. focus on a region and put the pen at the center of the region, and        3. move the pen smoothly to the center of the next region, and so forth until the curve was traced.        
This task cannot be easily automated, on a computer for example, because machines cannot “see” like a human, whose perception involves integration of local and global features. For computer vision, this is currently an unsolved problem.
The, so called, fuzzy c-means (FCM) algorithm and several fuzzy c-shells clustering algorithms have been used successfully to extract circular, elliptical and rectangular curves or lines in noisy data using a computer. These techniques are well known, and work well where the curve or line is represented by a small number of parameters, for example a circle can be uniquely described by its center and radius. In the clustering algorithm, the center of the circle corresponds to the center of a cluster and the radius to the average distance between the data samples and the center.
However, known clustering algorithms are only effective in dealing with a small number of curve shapes. In the real world, most curves cannot be described accurately by a mathematical formula or by a reasonably small number of parameters. Therefore, the clustering methods cannot be used to extract many real world curves. Also, the known techniques are not very effective when used on unordered and noisy curve data.